#include "stdafx.h"
#include "HashMap.h"

namespace hash_map{
	template<class Key, class Value>
	typename const HashMap<Key,Value>::Item* HashMap<Key,Value>::deleted=reinterpret_cast<typename const HashMap<Key,Value>::Item*>(-1);
	

	template<class Key,class Value>
	HashMap<Key,Value>::Iterator::Iterator(const HashMap<Key,Value>& hash_map)
		: map(hash_map),position(getNext(-1))
	{ }
 
	template<class Key,class Value>
	bool HashMap<Key,Value>::Iterator::operator!= (const Iterator& other) const
	{
		return position != other.position;
	}
 
	template<class Key,class Value>
	Key HashMap<Key,Value>::Iterator::operator* () const{
		if(position<map.capacity)
			return map.values[position].key;
		else throw "Out of range exception";
	}
 
	
	template<class Key,class Value>
	typename const HashMap<Key,Value>::Iterator& HashMap<Key,Value>::Iterator::operator++ ()
	{
		position=getNext(position);
		return *this;
	}


	template<class Key,class Value>
	int HashMap<Key,Value>::Iterator::getNext(int x)const{
		for(int res=++x; x<map.capacity; ++x)
			if(map.values[res]!=nullptr)
				return res;
		return map.capacity;		
	}

	
	template<class Key, class Value>
	HashMap<Key,Value>::HashMap():values(new Item*[start_capacity]),capacity(start_capacity),size(0)
	{
		for(int i=0; i<start_capacity; ++i)
			values[i]=nullptr;
	}
	
	template<class Key, class Value>
	HashMap<Key,Value>::~HashMap(){
		for(int i=0; i<start_capacity; ++i)
			if(values[i]!=nullptr)
				delete values[i];
		delete values;
	}

	template<class Key, class Value>
	int HashMap<Key,Value>::find(Key key, bool inserting)const
	{
		int index;
		for(int i=0; ; ++i)
		{
			index=hash(key.getHashCode(),i);
			if(values[i]==nullptr || (inserting && values[i]==deleted))
				return index;
		}
	}

	template<class Key, class Value>
	inline int HashMap<Key,Value>::hash(int main, int s)const{
		return (main+s*s)%capacity;
	}

	template<class Key, class Value>
	bool HashMap<Key,Value>::insert(Key key, Value value)
	{
		int pos=find(key);
		bool res=values[pos]==nullptr;
		if(res)values[pos]=new Item(key,value);
	
		if(res)++size;
		if(5*size>=4*capacity)
			rehash(capacity*2);
		return res;
	}

	template<class Key, class Value>
	bool HashMap<Key,Value>::remove(Key key){
		int pos=find(key);
		if(values[pos]==nullptr)return false;
		
		delete value[pos];
		value[pos]=deleted;
		--size;
		if(capacity>start_capacity && size < capacity/6)
			rehash(capacity/2); 
    }

	template<class Key, class Value>
	bool HashMap<Key,Value>::contains(Key key)const{
		Item*r=values[find(key)];
		return r!=nullptr && r!=deleted;
	}
		
	template<class Key, class Value>
	Value HashMap<Key,Value>::get(Key key)const{
		int pos=find(key);
		if(values[pos]==nullptr)throw "Key does not exists";
		return values[pos].value;
	}

	template<class Key, class Value>
	Value HashMap<Key,Value>::operator[](Key key)const{
		return get(key);
	}
	

	int pmain(){
		HashMap<AHashable<int>,int> map;
		//map.insert(4,5);
		return 9;
	}

}